/*
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 *
 *
 *
 *
 *
 * Written by Doug Lea and Josh Bloch with assistance from members of
 * JCP JSR-166 Expert Group and released to the public domain, as explained
 * at http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util;

/**
 * 一个线性的集合，支持在两端插入和删除元素。
 * deque是double ended queue 双端队列的简称，通常读作deck。
 * 绝大多数Deque实现对可以包含的元素的数量没有固定的限制，
 * 但这个接口支持容量限制的双端队列，也支持没有固定大小的。
 *
 * <p>这个接口定义了访问双端队列的两端末尾的元素。
 * 提供了插入，删除，返回这个元素的方法。
 * 它们的每个方法存在两个形式：如果操作失败，抛出异常。另个一个返回特殊值（null或者false，取决于操作）。
 * 后一种形式的插入操作专门用于容量受限的Queue实现。
 * 在大多数实现，insert操作不会失败。
 *
 * <p>上面的12个方法，在下表总结：
 *
 * <table BORDER CELLPADDING=3 CELLSPACING=1>
 * <caption>Deque 方法总结</caption>
 *  <tr>
 *    <td></td>
 *    <td ALIGN=CENTER COLSPAN = 2> <b>第一个元素（头）</b></td>
 *    <td ALIGN=CENTER COLSPAN = 2> <b>最后一个元素（尾）</b></td>
 *  </tr>
 *  <tr>
 *    <td></td>
 *    <td ALIGN=CENTER><em>抛出异常</em></td>
 *    <td ALIGN=CENTER><em>特殊值</em></td>
 *    <td ALIGN=CENTER><em>抛出异常</em></td>
 *    <td ALIGN=CENTER><em>特殊值</em></td>
 *  </tr>
 *  <tr>
 *    <td><b>插入</b></td>
 *    <td>{@link Deque#addFirst addFirst(e)}</td>
 *    <td>{@link Deque#offerFirst offerFirst(e)}</td>
 *    <td>{@link Deque#addLast addLast(e)}</td>
 *    <td>{@link Deque#offerLast offerLast(e)}</td>
 *  </tr>
 *  <tr>
 *    <td><b>删除</b></td>
 *    <td>{@link Deque#removeFirst removeFirst()}</td>
 *    <td>{@link Deque#pollFirst pollFirst()}</td>
 *    <td>{@link Deque#removeLast removeLast()}</td>
 *    <td>{@link Deque#pollLast pollLast()}</td>
 *  </tr>
 *  <tr>
 *    <td><b>返回</b></td>
 *    <td>{@link Deque#getFirst getFirst()}</td>
 *    <td>{@link Deque#peekFirst peekFirst()}</td>
 *    <td>{@link Deque#getLast getLast()}</td>
 *    <td>{@link Deque#peekLast peekLast()}</td>
 *  </tr>
 * </table>
 *
 * <p>这个接口继承了Queue接口。当一个双端队列被用作一个队列，产生FIFO（先进先出）的行为。
 * 元素被加入到双端队列的尾部，从头部被删除。
 * Queue接口继承来的方法与Deque的方法有几个等价，在下表显示：
 *
 * <table BORDER CELLPADDING=3 CELLSPACING=1>
 * <caption>Queue和Deque方法的比较</caption>
 *  <tr>
 *    <td ALIGN=CENTER> <b>{@code Queue}方法</b></td>
 *    <td ALIGN=CENTER> <b>等价的{@code Deque} 方法</b></td>
 *  </tr>
 *  <tr>
 *    <td>{@link java.util.Queue#add add(e)}</td>
 *    <td>{@link #addLast addLast(e)}</td>
 *  </tr>
 *  <tr>
 *    <td>{@link java.util.Queue#offer offer(e)}</td>
 *    <td>{@link #offerLast offerLast(e)}</td>
 *  </tr>
 *  <tr>
 *    <td>{@link java.util.Queue#remove remove()}</td>
 *    <td>{@link #removeFirst removeFirst()}</td>
 *  </tr>
 *  <tr>
 *    <td>{@link java.util.Queue#poll poll()}</td>
 *    <td>{@link #pollFirst pollFirst()}</td>
 *  </tr>
 *  <tr>
 *    <td>{@link java.util.Queue#element element()}</td>
 *    <td>{@link #getFirst getFirst()}</td>
 *  </tr>
 *  <tr>
 *    <td>{@link java.util.Queue#peek peek()}</td>
 *    <td>{@link #peek peekFirst()}</td>
 *  </tr>
 * </table>
 *
 * <p>Deque也可以被用做LIFO（后进先出）的栈。
 * 这个接口应该比Stack类优先使用。
 * 当一个deque被用作一个stack，元素从deque的开始处，插入和弹出。
 * stack的方法与deque的方法等价之处在下表显示：
 *
 * <table BORDER CELLPADDING=3 CELLSPACING=1>
 * <caption>比较 Stack 和 Deque 方法</caption>
 *  <tr>
 *    <td ALIGN=CENTER> <b>Stack 方法</b></td>
 *    <td ALIGN=CENTER> <b>等价的 {@code Deque} 方法</b></td>
 *  </tr>
 *  <tr>
 *    <td>{@link #push push(e)}</td>
 *    <td>{@link #addFirst addFirst(e)}</td>
 *  </tr>
 *  <tr>
 *    <td>{@link #pop pop()}</td>
 *    <td>{@link #removeFirst removeFirst()}</td>
 *  </tr>
 *  <tr>
 *    <td>{@link #peek peek()}</td>
 *    <td>{@link #peekFirst peekFirst()}</td>
 *  </tr>
 * </table>
 * 
 * <p>注意：peek方法在一个deque被用作queue或者stack时，效果一样。
 * 在任何一种情况，元素从deque的开始处，被拿出。
 * 
 * <p>这个接口提供了两个方法来移除内部的元素，
 * removeFirstOccurrence和removeLastOccurrence
 * 
 * <p>不像List接口，这个接口不提供，基于下标的对元素的访问。
 * 
 * <p>尽管Deque实现没有强制要求禁止插入null元素，但它强烈鼓励如此做。
 * 允许null元素的Deque实现的使用者，被鼓励不利用插入null的能力。
 * 因为null也被用于poll方法等多个方法的特殊返回值，表示队列没有元素。
 * 
 * <p>Deque实现通常不定义基于元素版本的equals和hashCode方法，
 * 反而继承了Object的基于标识的版本（即内存地址）
 *
 *
 * @author Doug Lea
 * @author Josh Bloch
 * @since  1.6
 * @param <E> the type of elements held in this collection
 */
public interface Deque<E> extends Queue<E> {
    /**
     * 如果能够立刻插入指定元素到双端队列的开始处，不违反容量的限制。
     * 如果此时没有可用的空间，抛出IllegalStateException
     * 当使用一个容量限制的双端队列，通常推荐使用offerFirst
     *
     * @param e the element to add
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */
    void addFirst(E e);

    /**
     * 如果能够立刻插入指定元素到双端队列的末尾处，不违反容量的限制。
     * 如果此时没有可用的空间，抛出IllegalStateException
     * 当使用一个容量限制的双端队列，通常推荐使用offerLast
     *
     * <p>这个方法与 add方法等价。注意：这个方法的返回值是void，add的返回值是boolean!
     *
     * @param e the element to add
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */
    void addLast(E e);

    /**
     * 插入指定元素到双端队列的开始处，除非违反容量的限制。成功，返回true。失败，返回false。
     * 当使用一个容量限制的双端队列，这个方法优先于addFirst，那个失败时，仅仅抛出一个异常。
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this deque, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */
    boolean offerFirst(E e);

    /**
     * 插入指定元素到双端队列的末尾处，除非违反容量的限制。成功，返回true。失败，返回false。
     * 当使用一个容量限制的双端队列，这个方法优先于addLast，那个失败时，仅仅抛出一个异常。
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this deque, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */
    boolean offerLast(E e);

    /**
     * 返回，并删除双端队列的第一个元素。
     * 这个方法与pollFirst的不同之处，仅是，如果双端队列为空，它抛出一个异常。
     *
     * @return the head of this deque
     * @throws NoSuchElementException if this deque is empty
     */
    E removeFirst();

    /**
     * 返回，并删除双端队列的最后一个元素。
     * 这个方法与pollLast的不同之处，仅是，如果双端队列为空，它抛出一个异常。
     *
     * @return the tail of this deque
     * @throws NoSuchElementException if this deque is empty
     */
    E removeLast();

    /**
     * 返回，并删除双端队列的第一个元素。
     * 或者，当双端队列为空，返回null。
     *
     * @return the head of this deque, or {@code null} if this deque is empty
     */
    E pollFirst();

    /**
     * 返回，并删除双端队列的最后一个元素。
     * 或者，当双端队列为空，返回null。
     *
     * @return the tail of this deque, or {@code null} if this deque is empty
     */
    E pollLast();

    /**
     * 返回，但是不删除双端队列的第一个元素。
     * 这个方法与peekFirst的不同之处，仅是，如果双端队列为空，它抛出一个异常。
     *
     * @return the head of this deque
     * @throws NoSuchElementException if this deque is empty
     */
    E getFirst();

    /**
     * 返回，但是不删除双端队列的最后一个元素。
     * 这个方法与peekLast的不同之处，仅是，如果双端队列为空，它抛出一个异常。
     *
     * @return the tail of this deque
     * @throws NoSuchElementException if this deque is empty
     */
    E getLast();

    /**
     * 返回，但是不删除双端队列的第一个元素。
     * 或者，如果双端队列为空，它返回null。
     *
     * @return the head of this deque, or {@code null} if this deque is empty
     */
    E peekFirst();

    /**
     * 返回，但是不删除双端队列的最后一个元素。
     * 或者，如果双端队列为空，它返回null。
     *
     * @return the tail of this deque, or {@code null} if this deque is empty
     */
    E peekLast();

    /**
     * 删除这个双端队列的第一次遇到的指定元素。
     * 如果不包含这个元素，它不改变。
     * 更正式地，删除第一个这样的元素e（如果存在），
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
     * 如果双端队列包含指定元素，返回true。（或者相同地，如果双端队列因为调用改变，返回true）
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if an element was removed as a result of this call
     * @throws ClassCastException if the class of the specified element
     *         is incompatible with this deque
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    boolean removeFirstOccurrence(Object o);

    /**
     * 删除这个双端队列的最后一次遇到的指定元素。
     * 如果不包含这个元素，它不改变。
     * 更正式地，删除最后一个这样的元素e（如果存在），
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
     * 如果双端队列包含指定元素，返回true。（或者相同地，如果双端队列因为调用改变，返回true）
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if an element was removed as a result of this call
     * @throws ClassCastException if the class of the specified element
     *         is incompatible with this deque
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    boolean removeLastOccurrence(Object o);

    // *** Queue 方法 ***

    /**
     * 如果能够立刻插入指定元素到由双端队列代表的队列（换言而之，在双端队列的尾部），不违反容量的限制，基于成功，返回true。
     * 如果此时没有可用的空间，抛出IllegalStateException。
     * 当使用一个容量限制的双端队列，推荐使用offer
     *
     * <p>这个方法与 {@link #addLast} 等价
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */
    boolean add(E e);

    /**
     * 如果能够立刻插入指定元素到由双端队列代表的队列（换言而之，在双端队列的尾部），不违反容量的限制，基于成功，返回true。
     * 如果此时没有可用的空间，返回false。
     * 当使用一个容量限制的双端队列，比add更好，因为add失败时，仅仅抛出一个异常。
     *
     * <p>这个方法与 {@link #offerLast} 等价
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this deque, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */
    boolean offer(E e);

    /**
     * 返回，并删除由双端队列代表的队列（换言而之，在双端队列的头部）的头部。
     * 这个方法与poll的不同之处为，如果队列为空，抛出异常。
     * 
     * <p>这个方法与 {@link #removeFirst} 等价
     *
     *
     * @return the head of the queue represented by this deque
     * @throws NoSuchElementException if this deque is empty
     */
    E remove();

    /**
     * 返回，并删除由双端队列代表的队列（换言而之，在双端队列的头部）的头部。
     * 如果队列为空，返回null。
     * 
     * <p>这个方法与 {@link #pollFirst} 等价
     *
     * @return the first element of this deque, or {@code null} if
     *         this deque is empty
     */
    E poll();

    /**
     * 返回，但不删除由双端队列代表的队列（换言而之，在双端队列的头部）的头部。
     * 这个方法与peek的不同之处为，如果队列为空，抛出异常。
     * 
     * <p>这个方法与 {@link #getFirst} 等价
     * 
     * @return the head of the queue represented by this deque
     * @throws NoSuchElementException if this deque is empty
     */
    E element();

    /**
     * 返回，但不删除由双端队列代表的队列（换言而之，在双端队列的头部）的头部。
     * 如果队列为空，返回null。
     * 
     * <p>这个方法与 {@link #peekFirst} 等价
     *
     * @return the head of the queue represented by this deque, or
     *         {@code null} if this deque is empty
     */
    E peek();


    // *** Stack 方法 ***

    /**
     * 如果能够立刻推入指定元素到由双端队列代表的栈（换言而之，在双端队列的头部），不违反容量的限制。
     * 如果此时没有可用的空间，抛出IllegalStateException。
     * 
     * <p>方法与 {@link #addFirst} 等价
     *
     * @param e the element to push
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */
    void push(E e);

    /**
     * 如果能够立刻弹出指定元素到由双端队列代表的栈（换言而之，在双端队列的头部），不违反容量的限制。
     * 如果此时没有元素，抛出NoSuchElementException。
     * 
     * <p>方法与 {@link #removeFirst} 等价
     *
     * @return the element at the front of this deque (which is the top
     *         of the stack represented by this deque)
     * @throws NoSuchElementException if this deque is empty
     */
    E pop();


    // *** Collection 方法 ***

    /**
     * 删除这个双端队列的第一次遇到的指定元素。
     * 如果不包含这个元素，它不改变。
     * 更正式地，删除第一个这样的元素e（如果存在），
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
     * 如果双端队列包含指定元素，返回true。（或者相同地，如果双端队列因为调用改变，返回true）
     * 
     * <p>这个方法与 {@link #removeFirstOccurrence(Object)} 等价
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if an element was removed as a result of this call
     * @throws ClassCastException if the class of the specified element
     *         is incompatible with this deque
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    boolean remove(Object o);

    /**
     * 如果这个双端队列包含指定的元素，返回true。
     * 更正式地，返回true，当且仅当双端队列包含至少一个这样的元素e，
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
     *
     * @param o element whose presence in this deque is to be tested
     * @return {@code true} if this deque contains the specified element
     * @throws ClassCastException if the type of the specified element
     *         is incompatible with this deque
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    boolean contains(Object o);

    /**
     * 返回双端队列的元素的数量。
     *
     * @return the number of elements in this deque
     */
    public int size();

    /**
     * 返回一个迭代器，覆盖双端队列的元素，以适当的顺序。
     * 返回的元素的顺序为：从第一个到最后一个（头部到尾部）
     *
     * @return an iterator over the elements in this deque in proper sequence
     */
    Iterator<E> iterator();

    /**
     * 返回一个迭代器，覆盖双端队列的元素，以适当的顺序。
     * 返回的元素的顺序为：从最后一个到第一个（尾部到头部）
     *
     * @return an iterator over the elements in this deque in reverse
     * sequence
     */
    Iterator<E> descendingIterator();

}
